<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <!-- 三角形最小路径和 -->
    <script>
      // var minimumTotal = function (triangle) {
      //   if (triangle.length === 0) return 0
      //   if (triangle.length === 1) return triangle[0][0]

      //   let d = [triangle[0][0]]
      //   let m = triangle.length

      //   for (let i = 1; i < m; i++) {
      //     let temp = []
      //     let arr = triangle[i]
      //     let len = arr.length
      //     temp[0] = d[0] + arr[0] //首尾两个数直接加上就好
      //     temp[len - 1] = d[d.length - 1] + arr[len - 1]
      //     for (let j = 1; j < len - 1; j++) {
      //       temp[j] = Math.min(d[j - 1], d[j]) + arr[j]
      //     }
      //     d = temp
      //   }

      //   return Math.min(...d)
      // }

      var minimumTotal = function (triangle) {
        const r = triangle.length,
          c = triangle[0].length
        // 构造动态规划路径
        const dp = new Array(r)
        for (let row = 0; row < r; row++) dp[row] = new Array(c)
        // 边界条件处理
        dp[0][0] = triangle[0][0]

        for (let i = 1; i < r; i++) {
          // 最左侧 dp[i][0] = dp[i-1][0] + triangle[i][0]
          dp[i][0] = dp[i - 1][0] + triangle[i][0]

          for (let j = 1; j < i; j++) {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j]
          }

          // 最右侧 dp[i][i] = dp[i-1][i-1] + triangle[i][i]
          dp[i][i] = dp[i - 1][i - 1] + triangle[i][i]
        }

        return Math.min(...dp[r - 1])
      }
      console.log(minimumTotal([[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]))
    </script>
  </body>
</html>
